#pragma once
#include <iostream>
#include "dsexceptions.h"
#include <algorithm>
using namespace std;

/// @brief 创建模板
/// @tparam DT 
template<typename DT>

/**
 * @brief 节点抽象类
 */
class Node
{
public:
	DT element; ///节点数据
	Node* left;    ///左指针
	Node* right;///右指针
public:
	/// @brief 虚拟函数，返回节点数据值
	/// @return DT
	virtual DT getElemnt() const { return element; }
	/// @brief 设置节点数据
	/// @param _val 
	virtual void setElemnt(DT _val) { element = _val; }
	/// @brief 初始化
	/// @param _val 
	Node(DT _val) { element = _val; }
};

/// @brief 创建模板
/// @tparam DT 
template<typename DT>
/**
 * @brief 二叉树抽象类
 */
class BinaryTree
{
public:
	/// @brief 插入数据
	/// @param _val 
	virtual void insert(DT && _val) = 0;
	/// @brief 删除数据
	/// @param _val 
	virtual void remove(DT && _val) = 0;
};

/// @brief 创建模板
/// @tparam DT 
template<typename DT>

/**
 * @brief 基于二叉树抽象类创建二叉搜索树类
 * 
 */
class BinarySearchTree : public BinaryTree<DT>
{
private:
    /**
     * @brief 基于节点抽象类创建二叉搜索树的节点类
     * 
     */
	class BinaryNode : public Node<DT>
	{
	public:
		BinaryNode* left;
		BinaryNode* right;
	public:
		BinaryNode(DT _val) : Node<DT>(_val)
		{
			left = nullptr;
			right = nullptr;
		}
	};

	BinaryNode* root = nullptr;
	
public:
	/// @brief 删除，调用重载函数remove()
	/// @param _val 
	virtual void remove(DT&& _val)
	{
		remove(std::move(_val), root);
	};

	BinaryNode* findMin(BinaryNode* t) const
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	}
	/// @brief 删除
	/// @param x 
	/// @param t 
	void remove(const DT& x, BinaryNode*& t)
	{
		if (t == nullptr)
			return;   // Item not found; do nothing
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) // Two children
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode* oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
	}
	/// @brief 插入，调用重载函数insert
	/// @param _val 
	virtual void insert(DT&& _val)
	{
		insert(std::move(_val), root);
	}
	/// @brief 插入操作
	/// @param _val 
	/// @param t 
	virtual void insert(DT && _val, BinaryNode*& t)
	{
		if (t == nullptr)
			t = new BinaryNode{_val};
		else if (std::move(_val) < t->element)
			insert(std::move(_val), t->left);
		else if (t->element < _val)
			insert(std::move(_val), t->right);
		else
			;  // Duplicate; do nothing
	}
	/// @brief 输出，调用重载函数printTree
	/// @param out 
	void printTree(ostream& out = cout) const
	{
		printTree(root, out);
		std::cout << std::endl;
	}
	/// @brief 输出操作
	/// @param t 
	/// @param out 
	void printTree(BinaryNode* t, ostream& out) const
	{
		if (t != nullptr)
		{
			printTree(t->left, out);
			out << t->element << "\t";
			printTree(t->right, out);
		}
	}

	~BinarySearchTree()
	{
		makeEmpty(root);
	}

	virtual void makeEmpty(BinaryNode*& t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}

};

/// @brief 创建模板
/// @tparam DT 
template<typename DT>

/**
 * @brief 基于二叉树抽象类创建平衡二叉树类
 * 
 */
class AvlTree : public BinaryTree<DT>
{
private:
    /**
     * @brief 基于节点抽象类创建平衡二叉树的节点类
     * 
     */
	class AvlNode : public Node<DT>
	{
	public:
		AvlNode* left;
		AvlNode* right;
		int height;
	public:
		AvlNode(DT _val) : Node<DT>(_val)
		{
			left = nullptr;
			right = nullptr;
			height = 0;
		}
	};

	AvlNode* root;
public:
	/// @brief 删除，调用重载函数remove
	/// @param _val 
	virtual void remove(DT&& _val)
	{
		remove(std::move(_val), root);
	};
	/// @brief 插入，调用重载函数insert
	/// @param _val 
	virtual void insert(DT&& _val)
	{
		insert(std::move(_val), root);
	};
	/// @brief 插入操作
	/// @param _val 
	/// @param t 
	void insert(const DT&& _val, AvlNode*& t)
	{
		if (t == nullptr)
			t = new AvlNode{ std::move(_val)};
		else if (std::move(_val) < t->element)
			insert(std::move(_val), t->left);
		else if (t->element < std::move(_val))
			insert(std::move(_val), t->right);

		balance(t);
	}
	/// @brief 删除操作
	/// @param x 
	/// @param t 
	void remove(const DT& x, AvlNode*& t)
	{
		if (t == nullptr)
			return;   // Item not found; do nothing

		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) // Two children
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			AvlNode* oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}

		balance(t);
	}

	void balance(AvlNode*& t)
	{
		if (t == nullptr)
			return;

		if (height(t->left) - height(t->right) > 1)
			if (height(t->left->left) >= height(t->left->right))
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
		else
			if (height(t->right) - height(t->left) > 1)
				if (height(t->right->right) >= height(t->right->left))
					rotateWithRightChild(t);
				else
					doubleWithRightChild(t);

		t->height = max(height(t->left), height(t->right)) + 1;
	}

	int height(AvlNode* t) const
	{
		return t == nullptr ? -1 : t->height;
	}
	/// @brief 删除，调用重载函数printTree
	void printTree() const
	{
		printTree(root);
		std::cout << std::endl;
	}
	/// @brief 输出
	/// @param t 
	void printTree(AvlNode* t) const
	{
		if (t != nullptr)
		{
			printTree(t->left);
			cout << t->element <<"\t";
			printTree(t->right);
		}
	}
	AvlNode* findMin(AvlNode* t) const
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	}

	void rotateWithRightChild(AvlNode*& k1)
	{
		AvlNode* k2 = k1->right;
		k1->right = k2->left;
		k2->left = k1;
		k1->height = max(height(k1->left), height(k1->right)) + 1;
		k2->height = max(height(k2->right), k1->height) + 1;
		k1 = k2;
	}

	void rotateWithLeftChild(AvlNode*& k2)
	{
		AvlNode* k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->height) + 1;
		k2 = k1;
	}

	void doubleWithLeftChild(AvlNode*& k3)
	{
		rotateWithRightChild(k3->left);
		rotateWithLeftChild(k3);
	}

	void doubleWithRightChild(AvlNode*& k1)
	{
		rotateWithLeftChild(k1->right);
		rotateWithRightChild(k1);
	}
};

/// @brief 创建模板
/// @tparam DT 
template <typename DT>
/**
 * @brief 基于二叉树抽象类创建伸展二叉树类
 * 
 */
class SplayTree: public BinaryTree<DT>
{
public:
    /**
     * @brief 基于节点抽象类创建伸展二叉树节点类
     * 
     */
    struct SplayTreeNode
    {
        DT  element;
        SplayTreeNode* left;
        SplayTreeNode* right;

        SplayTreeNode() : left{ nullptr }, right{ nullptr } { }

        SplayTreeNode(const DT& theElement, SplayTreeNode* lt, SplayTreeNode* rt)
            : element{ theElement }, left{ lt }, right{ rt } { }
    };
public:
    SplayTreeNode* root;
    SplayTreeNode* nullNode;

    SplayTree()
    {
        nullNode = new SplayTreeNode;
        nullNode->left = nullNode->right = nullNode;
        root = nullNode;
    }

    SplayTree(const SplayTree& rhs)
    {
        nullNode = new SplayTreeNode;
        nullNode->left = nullNode->right = nullNode;
        root = clone(rhs.root);
    }

    SplayTree(SplayTree&& rhs) : root{ rhs.root }, nullNode{ rhs.nullNode }
    {
        rhs.root = nullptr;
        rhs.nullNode = nullptr;
    }

    ~SplayTree()
    {
        makeEmpty();
        delete nullNode;
    }


    /**
     * Deep copy.
     */
    SplayTree& operator=(const SplayTree& rhs)
    {
        SplayTree copy = rhs;
        std::swap(*this, copy);
        return *this;
    }

    /**
     * Move.
     */
    SplayTree& operator=(SplayTree&& rhs)
    {
        std::swap(root, rhs.root);
        std::swap(nullNode, rhs.nullNode);

        return *this;
    }

    /**
     * Find the smallest item in the tree.
     * Not the most efficient implementation (uses two passes), but has correct
     *     amortized behavior.
     * A good alternative is to first call find with parameter
     *     smaller than any item in the tree, then call findMin.
     * Return the smallest item or throw UnderflowException if empty.
     */
    const DT& findMin()
    {
        if (isEmpty())
            throw UnderflowException{ };

        SplayTreeNode* ptr = root;

        while (ptr->left != nullNode)
            ptr = ptr->left;

        splay(ptr->element, root);
        return ptr->element;
    }

    /**
     * Find the largest item in the tree.
     * Not the most efficient implementation (uses two passes), but has correct
     *     amortized behavior.
     * A good alternative is to first call find with parameter
     *     larger than any item in the tree, then call findMax.
     * Return the largest item or throw UnderflowException if empty.
     */
    const DT& findMax()
    {
        if (isEmpty())
            throw UnderflowException{ };

        SplayTreeNode* ptr = root;

        while (ptr->right != nullNode)
            ptr = ptr->right;

        splay(ptr->element, root);
        return ptr->element;
    }


    bool contains(const DT& x)
    {
        if (isEmpty())
            return false;
        splay(x, root);
        return root->element == x;
    }

    bool isEmpty() const
    {
        return root == nullNode;
    }

    void printTree() const
    {
        std::cout << std::endl;
        printTree(root);
    }

    void makeEmpty()
    {
        /******************************
         * Comment this out, because it is prone to excessive
         * recursion on degenerate trees. Use alternate algorithm.

            reclaimMemory( root );
            root = nullNode;
         *******************************/
        while (!isEmpty())
        {
            findMax();        // Splay max item to root
            remove(root->element);
        }
    }

    virtual void insert(DT&& x)
    {
        static SplayTreeNode* newNode = nullptr;

        if (newNode == nullptr)
            newNode = new SplayTreeNode;
        newNode->element = x;

        if (root == nullNode)
        {
            newNode->left = newNode->right = nullNode;
            root = newNode;
        }
        else
        {
            splay(x, root);
            if (x < root->element)
            {
                newNode->left = root->left;
                newNode->right = root;
                root->left = nullNode;
                root = newNode;
            }
            else
                if (root->element < x)
                {
                    newNode->right = root->right;
                    newNode->left = root;
                    root->right = nullNode;
                    root = newNode;
                }
                else
                    return;
        }
        newNode = nullptr;   // So next insert will call new
    }

    void remove(DT && x)
    {
        // If x is found, it will be splayed to the root by contains
        if (!contains(x))
            return;   // Item not found; do nothing

        SplayTreeNode* newTree;

        if (root->left == nullNode)
            newTree = root->right;
        else
        {
            // Find the maximum in the left subtree
            // Splay it to the root; and then attach right child
            newTree = root->left;
            splay(x, newTree);
            newTree->right = root->right;
        }
        delete root;
        root = newTree;
    }

    void remove(const DT& x)
    {
        // If x is found, it will be splayed to the root by contains
        if (!contains(x))
            return;   // Item not found; do nothing

        SplayTreeNode* newTree;

        if (root->left == nullNode)
            newTree = root->right;
        else
        {
            // Find the maximum in the left subtree
            // Splay it to the root; and then attach right child
            newTree = root->left;
            splay(x, newTree);
            newTree->right = root->right;
        }
        delete root;
        root = newTree;
    }
public:

    /**
     * Internal method to reclaim internal nodes in subtree t.
     * WARNING: This is prone to running out of stack space.
     */
    void reclaimMemory(SplayTreeNode* t)
    {
        if (t != t->left)
        {
            reclaimMemory(t->left);
            reclaimMemory(t->right);
            delete t;
        }
    }

    /**
     * Internal method to print a subtree t in sorted order.
     * WARNING: This is prone to running out of stack space.
     */
    void printTree(SplayTreeNode* t) const
    {
        if (t != t->left)
        {
            printTree(t->left);
            cout << t->element << "\t";
            printTree(t->right);
        }
    }

    /**
     * Internal method to clone subtree.
     * WARNING: This is prone to running out of stack space.
     */
    SplayTreeNode* clone(SplayTreeNode* t) const
    {
        if (t == t->left)  // Cannot test against nullNode!!!
            return nullNode;
        else
            return new SplayTreeNode{ t->element, clone(t->left), clone(t->right) };
    }

    // Tree manipulations
    void rotateWithLeftChild(SplayTreeNode*& k2)
    {
        SplayTreeNode* k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2 = k1;
    }

    void rotateWithRightChild(SplayTreeNode*& k1)
    {
        SplayTreeNode* k2 = k1->right;
        k1->right = k2->left;
        k2->left = k1;
        k1 = k2;
    }

    /**
     * Internal method to perform a top-down splay.
     * The last accessed node becomes the new root.
     * This method may be overridden to use a different
     * splaying algorithm, however, the splay tree code
     * depends on the accessed item going to the root.
     * x is the target item to splay around.
     * t is the root of the subtree to splay.
     */
    void splay(const DT& x, SplayTreeNode*& t)
    {
        SplayTreeNode* leftTreeMax, * rightTreeMin;
        static SplayTreeNode header;

        header.left = header.right = nullNode;
        leftTreeMax = rightTreeMin = &header;

        nullNode->element = x;   // Guarantee a match

        for (; ; )
            if (x < t->element)
            {
                if (x < t->left->element)
                    rotateWithLeftChild(t);
                if (t->left == nullNode)
                    break;
                // Link Right
                rightTreeMin->left = t;
                rightTreeMin = t;
                t = t->left;
            }
            else if (t->element < x)
            {
                if (t->right->element < x)
                    rotateWithRightChild(t);
                if (t->right == nullNode)
                    break;
                // Link Left
                leftTreeMax->right = t;
                leftTreeMax = t;
                t = t->right;
            }
            else
                break;

        leftTreeMax->right = t->left;
        rightTreeMin->left = t->right;
        t->left = header.right;
        t->right = header.left;
    }
};